package com.dwliu.sort;

public class RadixSort {

	/**
	 * 基数排序，又称桶排序，分为最高位优先和最低位优先法
	 * 本例子是最低位优先法
	 * 1.根据个位数的数值，走访数组，将它们分配至0~9的桶中
	 * 2.将桶中的数值重新串联起来
	 * 3.再次分配，直至达到最高位
	 * @param a 数组
	 * @param m 位数
	 */
	public static void radixSort(int a[],int m){
		int len = a.length;
		//桶，二维数组，10 X len，保证能把所有的数都放在桶内（比如某次所有的都放在一个桶内）
		int[][] temparr = new int[10][len];
		//临时数组
		int b[] = new int[len];
		
		//迭代所有的位数
		for(int i=1; i<=m; i++){
			//初始化二维数组，全部为-1
			for(int s=0; s<10; s++){
				for(int t=0; t<len; t++){
					temparr[s][t] = -1;
				}
			}
			
			for(int j=0; j<len; j++){
				int radix = a[j]%10;
				
				//找到桶中的合适位置，并将数插入桶中
				int flag=0;
				while(temparr[radix][flag]!=-1){
					flag++;
				}
				
				//插入数据
				temparr[radix][flag] = a[j];
			}
			
			//拷贝数据到a数组中
			int index = 0;
			for(int s=0; s<10; s++){
				for(int t=0; t<len; t++){
					if(temparr[s][t]!=-1){
						a[index] = temparr[s][t];
						index++;
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// TODO Auto-generated method stub
		int a []= {1,6,3,4,5};
		for(int t: a)
			System.out.print(t+" ");
		System.out.println();
		radixSort(a,1);
		for(int t: a)
			System.out.print(t+" ");	
	}

}
